//
// Created by Lenovo on 2025/11/23.
//
#include "Prim.h"
#include<stdlib.h>

#include "Kruskal.h"

int Prim(MGraph *graph, int startv, EdgeSet *result) {
    //首先需要三个数组
    /*
     * cost：记录边的权值
     * marked：记录是否被激活
     * visited：记录指向该节点的上一个节点
     */
    int* cost=(int*)malloc(sizeof(int)*graph->nodeNum);
    int* marked = (int*)malloc(sizeof(int)*graph->nodeNum);//0代表未访问，1代表已访问
    int* visited = (int*)malloc(sizeof(int)*graph->nodeNum);
    //1、激活第一个节点并初始化
    for (int i = 0; i < graph->nodeNum; i++) {
        marked[i] = 0;
        cost[i] = graph->edge[startv][i];
        if (cost[i] < INF) {
            visited[i] = startv;
        }
        else {
            visited[i] = -1;
        }
    }
    marked[startv] = 1;

    //2、循环找到最小值，并修改cost数组与visited数组
    int k = 0;
    int min = INF;
    for (int i = 0; i < graph->nodeNum-1; i++) {
        min = INF;
        for (int j = 0; j < graph->nodeNum; j++) {
            if (marked[j]==0 && cost[j] < min) {
                min = cost[j];
                k = j;
            }
        }
        //此时找到了最小值，k即为最小值的下标
        marked[k]=1;//激活并存到边集数组里
        result[i].begin = visited[k];
        result[i].end = k;
        result[i].weight = min;
        //每激活一个节点，需要更新cost数组
        for (int j = 0; j < graph->nodeNum; j++) {
            if (marked[j]==0 && graph->edge[k][j]<cost[j]) {
                cost[j] = graph->edge[k][j];
                visited[j] = k;
            }
        }
    }
    free(cost);
    free(marked);
    free(visited);
}
